#include <iostream>
#include <cstring> // 用于memset等函数
using namespace std;

#define MAXPROCESS 50                        /*最大进程数*/
#define MAXRESOURCE 100                      /*最大资源数*/
int AVAILABLE[MAXRESOURCE];                  /*可用资源数组*/
int MAX[MAXPROCESS][MAXRESOURCE];            /*最大需求矩阵*/
int ALLOCATION[MAXPROCESS][MAXRESOURCE];     /*分配矩阵*/
int NEED[MAXPROCESS][MAXRESOURCE];           /*需求矩阵*/
int REQUEST[MAXPROCESS][MAXRESOURCE];        /*进程需要资源数*/
bool FINISH[MAXPROCESS];                     /*系统是否有足够的资源分配*/
int p[MAXPROCESS];                           /*记录序列*/
int m,n;                                     /*m个进程,n个资源*/

void Init();
bool Safe();
void Bank();
int main()
{
    // 清屏操作，适用于Linux终端
    system("clear");
    cout << "---------------银行家算法模拟实现---------------" << endl;

    a:  Init();
      if(!Safe()) goto a;	 
      Bank();
      return 0;
  
}

void Init()   /*初始化*/
{
    int i,j;
    cout << "请输入进程的数目m:";
    cin >> m;
    cout << "请输入资源的种类n:";
    cin >> n;
    cout << "请输入每个进程对资源数的最大需求,按照" << m << "x" << n << "矩阵输入" << endl;
    for(i=0;i<m;i++)
       for(j=0;j<n;j++)
          cin >> MAX[i][j];
    cout << "请输入每个进程已分配的资源数,同样按照" << m << "x" << n << "矩阵输入" << endl;
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
        {
            cin >> ALLOCATION[i][j];
            NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];
            if(NEED[i][j]<0)
            {
                cout << "进程" << i+1 << "的第" << j+1 << "个资源数超过其最大资源数,请重新输入:" << endl;
                j--;
				continue;
            }            
        }
    }
    cout << "请输入各个资源现有的数目:" << endl;
    for(i=0;i<n;i++)
    {
        cin >> AVAILABLE[i];
    }
	cout << "-------------------------------------------------------------------" << endl;
}

void Bank()  /*银行家算法*/
{
    int i,r;
    char again;
    while(1)
    {
        cout << "请输入要申请资源的进程号(注:第1个进程号为0,依次类推)" << endl;
        cin >> r;
        cout << "请输入进程所请求的各资源的数量" << endl;
        for(i=0;i<n;i++)
        {
            cin >> REQUEST[r][i];
        }
        for(i=0;i<n;i++)  
        {
            if(REQUEST[r][i]>NEED[r][i])
            {
                cout << "您输入的请求数超过进程的需求量!请重新输入!" << endl;
                break;
            }
            if(REQUEST[r][i]>AVAILABLE[i])
            {
                cout << "您输入的请求数超过系统现有的资源数!请重新输入!" << endl;
                break;
            }
        }
		if(i<n) continue;
        for(i=0;i<n;i++)
        {
            AVAILABLE[i]-=REQUEST[r][i];
            ALLOCATION[r][i]+=REQUEST[r][i];
            NEED[r][i]-=REQUEST[r][i];
        }
        if(Safe()) 
        {
            cout << "同意分配请求!" << endl;
        }
        else
        {
            cout << "您的请求被拒绝!" << endl;
            for(i=0;i<n;i++)  
            {
                AVAILABLE[i]+=REQUEST[r][i];
                ALLOCATION[r][i]-=REQUEST[r][i];
                NEED[r][i]+=REQUEST[r][i];
            }
        }
        cout << "您还想再次请求资源分配吗?是请按y/Y,否则请按其它键" << endl;
        cin >> again;
        if(again=='y'||again=='Y')
        {
            continue;
        }
        break;
        }
}

bool Safe()   /*安全性算法*/
{
    int i,j,k,l=0;
    int Work[MAXRESOURCE];                  
    for(i=0;i<n;i++)
        Work[i]=AVAILABLE[i];
    for(i=0;i<m;i++)      
    {
        FINISH[i]=false;
    }
    for(i=0;i<m;i++)
    {    
        if(FINISH[i]==true)
        {
            continue;
        }
        else      
        {
            for(j=0;j<n;j++)        //逐一检查现有资源是否满足进程i的需求
            {
                if(NEED[i][j]>Work[j])
                {
                    break;
                }
            }
            if(j==n)   
            { 
                FINISH[i]=true;
                for(k=0;k<n;k++)
                {
                    Work[k]+=ALLOCATION[i][k];//找到一个安全序列的进程节点后，改变工作数组work的值
                }
                p[l++]=i; //记录安全序列的进程编号
                i=-1;
            }
            else
            {
                continue; 
            }
	}
   }
   if(l==m)
   {
       cout << "系统是安全的" << endl;
       cout << "安全序列:" << endl;
       for(i=0;i<l;i++)
       {
           cout << p[i];
           if(i!=l-1)
           {
              cout << "-->";
           }
       }
       cout << "" << endl;
       return true;
   }
  else
  {
	  cout << "系统是不安全的" << endl;
	  return false;
  }  
}